package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/count-number-of-texts/
 * <p>
 * Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。
 * <p>
 * <p>
 * <p>
 * 为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。
 * <p>
 * 比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母  'k' 。
 * 注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不 使用它们。
 * 但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。
 * <p>
 * 比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。
 * 给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。
 * <p>
 * 由于答案可能很大，将它对 109 + 7 取余 后返回。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：pressedKeys = "22233"
 * 输出：8
 * 解释：
 * Alice 可能发出的文字信息包括：
 * "aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。
 * 由于总共有 8 种可能的信息，所以我们返回 8 。
 *
 * @author hanjuntao
 * @date 2025/7/24 0024
 */
public class L_2266_count_number_of_texts {

    public static void main(String[] args) {
        System.out.println(countTexts("22233"));
        // 8

        System.out.println(countTexts("222222222222222222222222222222222222"));
        // 82876089

        System.out.println(countTexts("444479999555588866"));
        // 3136

        System.out.println(countTexts("444444444444444444444444444444448888888888888888999999999999333333333333333366666666666666662222222222222222666666666666666633333333333333338888888888888888222222222222222244444444444444448888888888888222222222222222288888888888889999999999999999333333333444444664"));
        // 537551452

        System.out.println(countTexts(
                "88888888888888888888888888888999999999999999999999999999994444444444444444444444444444488888888888888888888888888888555555555555555555555555555556666666666666666666666666666666666666666666666666666666666222222222222222222222222222226666666666666666666666666666699999999999999999999999999999888888888888888888888888888885555555555555555555555555555577777777777777777777777777777444444444444444444444444444444444444444444444444444444444433333333333333333333333333333555555555555555555555555555556666666666666666666666666666644444444444444444444444444444999999999999999999999999999996666666666666666666666666666655555555555555555555555555555444444444444444444444444444448888888888888888888888888888855555555555555555555555555555555555555555555555555555555555555555555555555555555555999999999999999555555555555555555555555555554444444444444444444444444444444555"));
    }


    /**
     * 从题意可以，如果相连的数字相同，那么就可以看做排列问题（爬楼梯）
     * 我们只要将相连的数字进行分组，然后分别求组合数目，每组的结果乘起来，就是最终结果
     * <p>
     * 从题意可知，对于非7和9每一个数字，最多代表三个字母，对于数字7和9，代表四个字母。可以转化为爬楼梯问题：
     * <p>
     * 现在有N个重复的数字，代表N个台阶，求从1到N的台阶，有多少种走法。
     * 1. 对于数字7和9， 从一个台阶到下一个台阶，可以走1步，2步，3步，4步
     * 2. 对于非7和9， 从一个台阶到下一个台阶，可以走1步，2步，3步
     *
     * @param pressedKeys
     * @return
     */
    public static int countTexts(String pressedKeys) {
        long result = 1;
        long m = 1000000000 + 7;

        int i = 0;
        // 1. 获取当前数字
        // 2.一直向后读取数字，直到遇到非当前数据
        while (i < pressedKeys.length()) {
            char cur = pressedKeys.charAt(i);
            int j = i + 1;
            while (j < pressedKeys.length()) {
                char c = pressedKeys.charAt(j);

                if (c == cur) {
                    j = j + 1;
                } else {
                    break;
                }
            }

            int count = j - i;

            long cal = cal(count, cur, m);
            result = result * cal % m;

            //System.out.println("char:" + cur + "-count:" + count + "-cal:" + cal + "-result:" + result);

            i = j;
        }

        return (int) result;
    }

    public static long cal(int n, char c, long m) {
        if (n <= 2) {
            return n;
        }
        long[] dp = new long[n + 1];

        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        if (c == '7' || c == '9') {
            for (int i = 4; i <= n; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4]) % m;
            }
        } else {
            for (int i = 3; i <= n; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % m;
            }
        }

        return dp[n];
    }
}
